package nc;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n以内的自守数的个数
 * 功能: 求出n以内的自守数的个数
 *
 *
 * 输入参数：
 * int n
 *
 * 返回值：
 * n以内自守数的数量。
 */
public class Q21322 {

    // 优化算法
    // 可以证明，某一个自首数，其尾数必须也是自守数
    // 根据此算法可以优化
    public static List<Integer> resolve2(int n) {
        List<Integer> nums = new ArrayList<>();
        // 先放10以内的
        for (int i = 0; i < 10 && i <= n; i++) {
            int num = i * i;
            if (num % 10 == i) {
                nums.add(i);
            }
        }
        if (n < 10) {
            return nums;
        }
        for (int k = 10;n / k != 0;k*=10) {
            List<Integer> newNums = new ArrayList<>();
            for (int i = 1; i < 10 && i * k <= n; i++) {
                for (Integer num : nums) {
                    int l = i * k + num;
                    if (l > n) {
                        break;
                    }
                    if ((l * l) % (k*10) ==l) {
                        // 加到一个数组中
                        newNums.add(l);
                    }
                }
            }
            nums.addAll(newNums);
        }

        return nums;
    }

    public static List<Integer> resolve(int n) {
        List<Integer> nums = new ArrayList<>();
        int k = 10;
        for (int i = 0; i < n; i++) {
            // 判断一个数的尾数是否为
            int num = i * i;
            // 判断几位数？
            if (i / k != 0) {
                // 判断是不是升级了
                k *= 10;
            }
            if (num % k == i) {
                nums.add(i);
            }
        }
        return nums;
    }

    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()) {
//            final int n = scanner.nextInt();
//            System.out.println(resolve(n).size());
//        }
        System.out.println(resolve2(10000));
    }

}
